package com.hqq.graph;

/**
 * DeepGraphSearch
 * 深度优先遍历图
 * Created by heqianqian on 2017/8/6.
 */
public class DeepGraphSearch implements GraphSearch {

    /**
     * 保存是否遍历节点的数组
     */
    private boolean[] marked;
    /**
     * 当前已遍历节点个数
     */
    private int count;

    public DeepGraphSearch(Graph graph, int s) {
        marked = new boolean[graph.vertexCount()];
        dfs(graph, s);
    }

    private void dfs(Graph graph, int s) {
        marked[s] = true;
        this.count++;
        for (int w : graph.adjVertex(s)) {
            if (!marked[w]) {
               dfs(graph,w);
            }
        }
    }

    @Override
    public boolean marked(int v) {
        return marked[v];
    }

    @Override
    public int count() {
        return this.count;
    }
}
